// Package _1_判断一个链表是否是回文结构 main
// @Title _1_判断一个链表是否是回文结构
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-14 10:52
// @Create  2022-01-14 10:52
package main

import "fmt"

type LinkList struct {
	Val  int
	Next *LinkList
}

func main() {
	// 构造一个回文链表
	head := LinkList{
		1,
		&LinkList{
			2,
			&LinkList{
				3,
				&LinkList{
					2,
					&LinkList{
						1,
						nil,
					},
				},
			},
		},
	}
	//fmt.Println(isPalindromeLinkList(&head))
	fmt.Println(isPalindromeLinkListFastPoint(&head))
	fmt.Println(isPalindromeLinkListO1(&head))
}

//
//  isPalindromeLinkList
//  @Description: 判断一个链表是否是回文链表  思路1 用栈！ O(N)
//  @param head： 链表的头指针
//  @return bool：是否是回文链表
//
func isPalindromeLinkList(head *LinkList) bool {
	if head == nil {
		return false
	}
	var linkArr []int // 记录链表的值的数组
	for p := head; p != nil; p = p.Next {
		linkArr = append(linkArr, p.Val)
	}
	// 2. 判断数组是否是回文数组
	for i := 0; i < len(linkArr)/2; i++ {
		if linkArr[i] != linkArr[len(linkArr)-1-i] {
			return false
		}
	}
	return true
}

// 有没有更快的方式呢？  快慢指针

//
//  isPalindromeLinkListFastPoint
//  @Description: 使用快慢指针完成判断链表是否回文  慢指针一次走一步，快指针一次两步，快的到头来，慢的正好在中间 要分基数和偶数情况
//  @param head：
//  @return bool：
//
func isPalindromeLinkListFastPoint(head *LinkList) bool {
	if head == nil || head.Next == nil {
		return true
	}
	slow := head.Next
	fast := head
	for fast.Next != nil && fast.Next.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	// 创建一个栈
	stack := []*LinkList{}
	for slow != nil {
		stack = append(stack, slow)
		slow = slow.Next
	}
	for len(stack) > 0 {
		tVal := stack[len(stack)-1].Val
		stack = stack[:len(stack)-1]
		if head.Val != tVal {
			return false
		}
		head = head.Next
	}
	return true
}

//
//  isPalindromeLinkListO1
//  @Description: 压缩空间的算法  这思路不是很秀，但是很考验coding能力
//  @param head：
//  @return bool：
//
func isPalindromeLinkListO1(head *LinkList) bool {
	if head == nil || head.Next == nil {
		return true
	}
	n1, n2 := head, head
	for n2.Next != nil && n2.Next.Next != nil {
		n1 = n1.Next      // 慢指针一次走一步
		n2 = n2.Next.Next // 快指针一次走两步
	}
	n2 = n1.Next
	n1.Next = nil
	var n3 *LinkList
	// 将右半部分逆序
	for n2 != nil {
		n3 = n2.Next
		n2.Next = n1
		n1 = n2
		n2 = n3
	}
	n3 = n1
	n2 = head
	var res bool = true
	for n1 != nil && n2 != nil {
		if n1.Val != n2.Val {
			res = false
			break
		}
		n1 = n1.Next
		n2 = n2.Next
	}
	n1 = n3.Next
	n3.Next = nil
	// 返回之前，对链表还原
	for n1 != nil {
		n2 = n1.Next
		n1.Next = n3
		n3 = n1
		n1 = n2
	}
	return res
}
